#include "floyd_warshall.h"

// 更新原始距离矩阵
void floydWarshall(QVector<QVector<double>> &distanceMatrix) {
    int n = distanceMatrix.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (distanceMatrix[i][k] + distanceMatrix[k][j] < distanceMatrix[i][j]) {
                    distanceMatrix[i][j] = distanceMatrix[i][k] + distanceMatrix[k][j];
                }
            }
        }
    }
}

// 返回更新后的距离矩阵
QVector<QVector<double>> floyd(QVector<QVector<double>> distanceMatrix) {
    int n = distanceMatrix.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (distanceMatrix[i][k] + distanceMatrix[k][j] < distanceMatrix[i][j]) {
                    distanceMatrix[i][j] = distanceMatrix[i][k] + distanceMatrix[k][j];
                }
            }
        }
    }
    return distanceMatrix;
}
//深度优先搜索
void dfs(int node, const QVector<QVector<double>> &distanceMatrix, QVector<bool> &visited, QVector<int> &component, int componentIndex) {
    visited[node] = true;
    component[node] = componentIndex;
    for (int i = 0; i < distanceMatrix.size(); ++i) {
        if (distanceMatrix[node][i] != std::numeric_limits<double>::infinity() && !visited[i]) {
            dfs(i, distanceMatrix, visited, component, componentIndex);
        }
    }
}
//连通分量计算
int countConnectedComponents(const QVector<QVector<double>> &distanceMatrix, QVector<int> &component) {
    int n = distanceMatrix.size();
    QVector<bool> visited(n, false);
    int connectedComponents = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, distanceMatrix, visited, component, connectedComponents);
            connectedComponents++;
        }
    }

    return connectedComponents;
}
